#include <mpi.h>
#include <limits.h> //INT_NAX#include <stdlib.h> //abs#include <string.h> //memcpy#include <stdio.h>

enum {
	INFOTAG = 73,
	FINISH = 25,
	PREFIXSIZE = 2,
	ROOT = 0,
};

struct problem_t {
	int n;
	const int* xs;
	const int* ys;
} p;

int f(int i, int j) {
	return abs(p.xs[i] - p.xs[j]) + abs(p.ys[i] - p.ys[j]);
}

int get_acyclic_path_weight(int n, int path[]) {
	int d = 0;
	for (int i = 0; i < n - 1; i++)
		d += f(path[i], path[i + 1]);
	return d;
}

typedef struct {
	int weight;
	int* const path;
} solution_t;

void intcopy(void* dst, void* src, size_t count) {
	memcpy(dst, src, count * sizeof(int));
}

enum packed_t {
	WEIGHT_OFFSET, CITIES_NUM_OFFSET, PATH_OFFSET
};
#define PACKED_SIZE(citiesNum) ((citiesNum)+2)
#define LEN(arr) (sizeof(arr) / sizeof(arr[0]))
MPI_Datatype build_derived_type(int citiesNum) {
	MPI_Aint disp[] = { WEIGHT_OFFSET * sizeof(int), CITIES_NUM_OFFSET
			* sizeof(int), PATH_OFFSET * sizeof(int) };
	int counts[LEN(disp)] = { 1, 1, citiesNum, };
	MPI_Datatype list[LEN(disp)] = { MPI_INT, MPI_INT, MPI_INT };

	MPI_Datatype mpiType;
	MPI_Type_struct(LEN(disp), counts, disp, list, &mpiType);

	MPI_Type_commit(&mpiType);
	return mpiType;
}

// The static parellel algorithm main function.
void do_tsp(int prefix_path[], int path[]);

int get_rank(void) {
	int rank;
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	return rank;
}

int get_num_threads(void) {
	int numOfThreads;
	MPI_Comm_size(MPI_COMM_WORLD, &numOfThreads);
	return numOfThreads;
}

void print_path(int citiesNum, int path[]) {
	for (int i = 0; i < citiesNum; i++)
		printf("%d ", path[i]);
	printf("\n");
}

/*
 * MASTER
 */

static int used(int arr[], int top) {
	const int x = arr[top];
	for (int i = 0; i < top; i++)
		if (arr[i] == x)
			return 1;
	return 0;
}

static int next_permutation(int arr[], int len) {
	const int top = len - 1;
	for (;;) {
		do {
			arr[top]++;
		} while (used(arr, top));
		if (arr[top] != p.n)
			return 1;
		if (top == 1 || !next_permutation(arr, top))
			return 0;
		arr[top] = 0;
	}
	return 0;
}

int receive_send(solution_t perfix, int path[]) {
	MPI_Status mpi_status;
	MPI_Recv(path, 			p.n, 	MPI_INT, MPI_ANY_SOURCE, INFOTAG,
			 MPI_COMM_WORLD, &mpi_status);
	print_path(p.n, path);
	MPI_Send(perfix.path, PREFIXSIZE,	MPI_INT, mpi_status.MPI_SOURCE, INFOTAG,
			 MPI_COMM_WORLD);
//	MPI_Sendrecv(perfix.path, PREFIXSIZE,	MPI_INT, MPI_ANY_SOURCE, INFOTAG,
//				 path, 			p.n, 		MPI_INT, MPI_ANY_SOURCE, INFOTAG,
//				 MPI_COMM_WORLD, &mpi_status);
	return 1;
}

int master(int shortestPath[]) {
	int nthreads = get_num_threads();
	int prefix_path[PREFIXSIZE];
	for (int i=0; i < PREFIXSIZE; i++)
		prefix_path[i] = i;

	solution_t prefix = { 0, prefix_path };
	solution_t sol = { INT_MAX, shortestPath };
	int more = 1;
	MPI_Status mpi_status;
	while (nthreads > 1) {
		int path[p.n];
		MPI_Recv(path, p.n, MPI_INT, MPI_ANY_SOURCE, INFOTAG, MPI_COMM_WORLD, &mpi_status);
		print_path(p.n, path);
		int next_weight = get_acyclic_path_weight(p.n, path) + f(path[p.n-1], path[0]);
		if (next_weight < sol.weight) {
			sol.weight = next_weight;
			intcopy(sol.path, path, p.n);
		}

		more = more && next_permutation(prefix_path, PREFIXSIZE);
		if (!more)
			--nthreads;
		MPI_Send(prefix.path, PREFIXSIZE,	MPI_INT, mpi_status.MPI_SOURCE, more ? INFOTAG : FINISH, MPI_COMM_WORLD);
		//receive_send(prefix, path);
	}
	return sol.weight;
}

/*
 * WORKER
 */

int worker_send_fetch(int path[], int prefix_out[]) {
	MPI_Status mpi_status;
	int rank = get_rank();
	printf("%d: 1\n", rank);
	MPI_Sendrecv(path,  p.n,		MPI_INT, ROOT, INFOTAG,
				prefix_out, PREFIXSIZE, MPI_INT, ROOT, MPI_ANY_TAG,
				MPI_COMM_WORLD, &mpi_status);
	printf("%d: 2. tag = %d\n", rank, mpi_status.MPI_TAG);
	return mpi_status.MPI_TAG != FINISH;
}

int worker(void) {
	int prefix[p.n];
	int path[p.n];
	for (int i=0; i < p.n; i++)
		path[i] = i;
	while ((worker_send_fetch(path, prefix))) {
		do_tsp(prefix, path);
	}
	return 0;
}

/*
 * TSP
 */

//return weight of the minimal solution
void tsp_recurse(int path[], int used[], const int len, const int weight,
		solution_t* min) {
	if (len == p.n) {
		const int new_weight = weight + f(path[len - 1], path[0]);
		if (new_weight < min->weight) {
			intcopy(min->path, path, p.n);
			min->weight = new_weight;
		}
	}
	for (int i = 0; i < p.n; i++) {
		if (used[i])
			continue;
		const int new_weight = weight + f(path[len - 1], i);
		if (new_weight >= min->weight)
			continue;

		path[len] = i;
		used[i] = 1;
		tsp_recurse(path, used, len + 1, new_weight, min);
		used[i] = 0;
	}
}

void do_tsp(int prefix_path[], int path[]) {

	solution_t sol = { .weight = INT_MAX , .path = path };
	int used[p.n];
	memset(used, 0, p.n * sizeof(int));
	for (int i = 0; i < PREFIXSIZE; i++)
		used[prefix_path[i]] = 1;
	tsp_recurse(prefix_path, used, PREFIXSIZE,
			get_acyclic_path_weight(PREFIXSIZE, prefix_path), &sol);
}

//#define TEST

#ifndef TEST
int tsp_main(int citiesNum, int xCoord[], int yCoord[], int shortestPath[]) {
	struct problem_t pp = {.n = citiesNum, .xs = xCoord, .ys = yCoord,};
	p = pp;
	if (get_rank()) {
		printf("worker\n");
		return worker();
	}
	return master(shortestPath);
}
#endif
